The present invention relates to performance enhancement and deadlock prevention in a multiple texture pipeline graphics processor. More specifically, the invention relates to a method and apparatus for balancing and synchronizing the memory requests issued by multiple parallel texture pipelines. As polygon textures are processed by a texture engine, a memory request arbitrator ensures that all of the memory requests associated with a portion of a given graphics texture are issued by all texture pipelines before any single texture pipeline may issue a memory request for another portion of a graphics texture.
Many prior art computer graphics devices have the ability to display polygons with two-dimensional texture images (“textures”) mapped onto them. These textures give graphics objects a realistic or life-like appearance. For example, a texture may be a picture of a brick facade for application to a collection of polygons that together represent the three-dimensional framework of a house. Or, alternatively, a wood grain texture may be applied to a collection of polygonal objects that together form the shape of a desk.
As is known, a graphics processor may be organized as a pipeline in which each pipe section performs a sequence of processing steps. As a whole, these individual pipe sections generate picture images composed of graphics objects. Each of these graphics objects are typically composed of triangles that are themselves divided into spans, each span corresponding to a matrix of pixels. For example, a span may be composed of 16 pixels arranged in a (4×4) matrix. The individual sections of a pipelined graphics processor may process data on a span-by-span basis.
Pipelined graphics processors typically contain a texture engine for the purpose of applying textures to the surfaces of graphics objects. The individual components of a texture engine are usually arranged in a pipeline as well, thereby achieving additional efficiency. The final product of a texture engine consists of an output stream of “texels” corresponding to the picture elements of texture-mapped polygons.
For an extended treatment on methods of graphics visualization and texture mapping, see Foley, van Dam, et al., Computer Graphics-Principles and Practice (2d Ed. 1990 Addison Wesley, corr. 1995).
Multi-texturing is a general technique known in the art for blending textures together to create a multi-textured effect. Linear filtering and trilinear filtering are examples of multi-texturing techniques that blend adjacent levels of the same texture. As is also known, entirely different textures may also be blended to create a variety of visual effects.
A conventional single texture pipeline may implement texture blending by processing each texture one at a time, and then blending the results. In this single pipeline architecture, all of the memory requests associated with additional textures are issued after all of the memory requests have been issued for the first texture. The resulting textures are then combined in a separate blending stage. Because a texture blending unit may require the data from all component textures to be available at the same time, the texels of the first texture must be produced first and held in a buffer. When the texels of the remaining textures are produced, the final combined texture may be output by the texture blending unit by combining the buffered texels of the first texture with the produced texels of the remaining textures. Alternatively, the texels of the remaining textures may also be buffered before they are combined with the first texture. In a single pipeline architecture, because the individual textures are calculated serially, there is no need to synchronize or balance the processing of the multiple component textures.
To improve the processing speed of multi-texturing operations, separate texture pipelines may be configured to operate in parallel. In such a multiple texture pipeline architecture, each individual texture pipeline may operate independently and may request texel data from memory at its own pace. The data returning from memory may be stored in separate buffers corresponding to each texture pipeline. Because texture pipelines may work autonomously and may simultaneously process different textures, each having a different size and complexity, the output buffers for texture pipelines may fill up at different rates. In this situation, one output buffer may be full while another output buffer remains empty. Thus, where more than one texture is associated with a polygon and each texture is processed by a different texture pipeline, a deadlock condition may occur when one texture pipeline is waiting for a downstream texture blending unit to begin processing its buffered texture data, but the texture blending unit is unable to begin the next blending operation because the buffer for another texture pipeline does not yet contain the required texture data. The deadlock is created when the first texture pipeline, which is waiting for its output buffer to be cleared by the texture blending unit, issues a successful memory request. Under these conditions, this memory request will never complete. Because the first texture pipeline's output buffer is full (and cannot empty because the texture blending unit is waiting for data from another texture pipeline), its data returning from memory cannot be stored. At the same time, the other texture pipelines cannot proceed because there is an outstanding memory request from the first texture pipeline that is currently being served. Closing the deadlock is the texture blending unit, which cannot proceed because it does not have the necessary data from all required texture pipelines to begin the blending operation.
Accordingly, there is a need in the art for a technique to balance and synchronize the operation of parallel texture pipelines to improve processing efficiency and to prevent deadlock conditions. More specifically, there is a need in the art for a technique to arbitrate and balance the memory requests issued by parallel texture pipelines in a multiple pipeline texture engine. Finally, there is a need in the art to synchronize the operation of parallel texture pipelines while also permitting unsynchronized memory requests to be satisfied if the requested data resides in cache memory.